<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 合并两个有序数组：先把值负值到临时数组，再合并回去
        var mergeOfTwoSortedArray = function (nums, left, mid, right) {
            let len = right - left + 1;
            let temp = new Array(len);

            for (let i = 0; i < len; i++) {
                temp[i] = nums[left + i];
            }

            // i和j分别指向前有序数组和后有序数组的起始位置 
            let i = 0,
                j = mid - left + 1;
            for (let k = 0; k < len; k++) {
                if (i === mid + 1 - left) {
                    nums[left + k] = temp[j];
                    j++;
                } else if (j === right + 1 - left) {
                    nums[left + k] = temp[i];
                    i++;
                } else if (temp[i] <= temp[j]) {
                    nums[left + k] = temp[i];
                    i++;
                } else {
                    nums[left + k] = temp[j];
                    j++;
                }
            }

        }

        // 归并排序
        var mergeSort = function (nums, left, right) {
            if (left === right) {
                return;
            }

            let mid = parseInt(left + (right - left) / 2);
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            mergeOfTwoSortedArray(nums, left, mid, right);
        }

        var sortArray = function (nums) {
            let len = nums.length;
            mergeSort(nums, 0, len - 1);
            return nums;
        }
    </script>
</body>

</html>